package com.jp.algorithm;

import java.util.Stack;

public class LargestRectangleArea {

    public static int  largestRectangleArea(int[] heights) {
        if(heights.length==0)
            return 0;
        if(heights.length==1)
            return heights[0];
        int l=heights.length;
        int max=0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<=l;i++){
            while(!stack.isEmpty() && (heights[i] < heights[stack.peek()] || i==l)){
                int height = heights[stack.pop()];
                int width = stack.isEmpty()? i : i-1-stack.peek();
                max = Math.max(height*width, max);
            }
            stack.push(i);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] weights = {2,1,5,6,2,3};
        System.out.println(largestRectangleArea(weights));
    }
}
